package com.leetcode.algorithm.y22.m07.w5;

import java.util.ArrayList;
import java.util.List;

import com.leetcode.algorithm.common.ListNode;

/**
 * 剑指 Offer II 078. 合并排序链表
 * 
 * https://leetcode.cn/problems/vvXgSW/
 * 
 * @author jie.deng
 *
 */
class QuestionOffer2078Solution01 {

	public ListNode mergeKLists(ListNode[] lists) {
		ListNode sentinel = new ListNode();
		ListNode cur = sentinel;
		List<ListNode> curList = new ArrayList<>();
		for (ListNode tmp : lists) {
			if (tmp != null) {
				curList.add(tmp);
			}
		}
		while (!curList.isEmpty()) {
			ListNode min = null;
			int minIdx = -1;
			for (int i = 0; i < curList.size(); i++) {
				ListNode tmp = curList.get(i);
				if (min == null || tmp.val < min.val) {
					min = tmp;
					minIdx = i;
				}
			}
			if (min != null) {
				cur.next = new ListNode(min.val);
				if (min.next == null) {
					curList.remove(minIdx);
				} else {
					ListNode tmp = curList.get(minIdx);
					curList.set(minIdx, tmp.next);
				}
				cur = cur.next;
			}
		}

		return sentinel.next;
	}

}